Celestin Apprentice 7/Apprentice-Release7.iso/Source Code/C ++/Frameworks/MacZoop 1.6.5/Basic Classes/Z Sources/ZArray.cpp

C/C++ Source or Header | 1997-05-09 | 14.2 KB | 573 lines | [TEXT/CWIE]

/*************************************************************************************************
*
*
*            ObjectMacZapp        -- a standard Mac OOP application template
*
*
*
*            ZArray.cpp            -- the basic container class object
*
*
*
*
*
*            © 1996, Graham Cox
*
*
*
*
*************************************************************************************************/


#include    "ZArray.h"
#include    "MacZoop.h"


static short    vCompareFunc( void* a, void* b, const long ref);


/*-------------------------------***  CONSTRUCTOR  ***----------------------------------*/


ZArray::ZArray( short elementSize )
    : ZComrade()
{
    blkSize = elementSize;
    numElements = 0;

    FailNIL(a = NewHandle( 0 ));
}

/*--------------------------------***  DESTRUCTOR  ***----------------------------------*/

ZArray::~ZArray()
{
    if (a)
        DisposeHandle( a );
}


/*--------------------------------***  INSERTITEM  ***----------------------------------*/
/*
Insert an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::InsertItem(void* item, const long index)
{
    // insert the item into the array at position <index>. The value of <index> is one-based.
    // This extends the array by one item.

    InsertElement( index - 1 );
    SetArrayItem( item, index );

    SendMessage( msgArrayItemInserted, (void*) index );
}


/*--------------------------------***  APPENDITEM  ***----------------------------------*/
/*
add an item at the end of the array
----------------------------------------------------------------------------------------*/

void    ZArray::AppendItem(void* item)
{
    // adds the item to the end of the array. This grows it by one item.

    InsertElement( numElements );
    SetArrayItem( item, numElements );

    SendMessage( msgArrayItemAdded, (void*) numElements );
}


/*-------------------------------***  SETARRAYITEM  ***---------------------------------*/
/*
replace an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::SetArrayItem(void* item, const long index)
{
    // sets the item into the array at <index>, which is one-based.

    if ((index < 1) || (index > numElements))
        FailOSErr( kIndexOutOfRangeErr );

    BlockMoveData(item, (*a + (blkSize * (index - 1))), blkSize);

    SendMessage( msgArrayItemChanged, (void*) index );
}


/*-------------------------------***  GETARRAYITEM  ***---------------------------------*/
/*
return the item at position <index> (returns a COPY)
----------------------------------------------------------------------------------------*/

void    ZArray::GetArrayItem(void* item, const long index)
{
    // gets the item at poition <index> in the array. Index is one-based.

    if ((index < 1) || (index > numElements))
        FailOSErr( kIndexOutOfRangeErr );

    BlockMoveData((*a + (blkSize * (index - 1))), item, blkSize);
}


/*---------------------------------***  FINDINDEX  ***----------------------------------*/
/*
returns the index of an item in the array, or 0 if not found.
----------------------------------------------------------------------------------------*/

long    ZArray::FindIndex(void* item)
{
    // performs a linear search and returns the index of the item, if found.

    if ( numElements < 1 )
        return 0;

    long        i = 0;
    Boolean        found = FALSE;

    do
    {
        if (EqualMem(*a + ( blkSize * i ), item, blkSize))
        {
            found = TRUE;
            break;
        }
    }
    while( i++ < numElements );

    return ( found? i + 1 : 0 );
}

/*--------------------------------***  DELETEITEM  ***----------------------------------*/
/*
Delete an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::DeleteItem( const long index )
{
    // deletes the item at position <index> (1-based). Items above are moved down one.

    DeleteElement( index - 1 );

    SendMessage( msgArrayItemDeleted, (void*) index );
}


/*----------------------------------***  MOVEITEM  ***----------------------------------*/
/*
move an item from one place in the array to another
----------------------------------------------------------------------------------------*/

void    ZArray::MoveItem( const long curIndex, const long newIndex )
{
    // moves the item at <curIndex> to position <newIndex> (all 1-based), moving other items
    // as needed to keep things in order.

    if ((curIndex < 1) ||
        (curIndex > numElements) ||
        (newIndex < 1) ||
        (newIndex > numElements))
        FailOSErr( kIndexOutOfRangeErr );

    void* temp = (void*) NewPtr( blkSize );

    FailNIL(temp);

    // copy the item we want to move to a temporary space

    GetArrayItem( temp, curIndex);

    // delete its current position, which will move stuff as needed

    DeleteElement( curIndex - 1 );

    // insert it into the new position, which moves other stuff as needed

    InsertItem( temp, newIndex );

    // get rid of the temporary space

    DisposePtr((Ptr) temp);
    SendMessage( msgArrayItemMoved, (void*) newIndex );
}


/*----------------------------------***  SWAPITEM  ***----------------------------------*/
/*
Swap two items in the array
----------------------------------------------------------------------------------------*/

void    ZArray::Swap( const long itema, const long itemb )
{
    // swaps items a and b.
    if ((itema < 1) ||
        (itema > numElements) ||
        (itemb < 1) ||
        (itemb > numElements))
        FailOSErr( kIndexOutOfRangeErr );

    // make some swap space

    void* tempa = (void*) NewPtr( blkSize );
    void* tempb = (void*) NewPtr( blkSize );
    FailNIL(tempa);
    FailNIL(tempb);

    GetArrayItem( tempa, itema);
    GetArrayItem( tempb, itemb);
    SetArrayItem( tempa, itemb);
    SetArrayItem( tempb, itema);

    DisposePtr((Ptr) tempa);
    DisposePtr((Ptr) tempb);

    SendMessage( msgArrayItemMoved, (void*) itema );
}


/*---------------------------------***  COUNTITEMS  ***---------------------------------*/
/*
return the number of items in the array
----------------------------------------------------------------------------------------*/

long    ZArray::CountItems()
{
    return numElements;
}


/*----------------------------------***  DOFOREACH  ***---------------------------------*/
/*
for each item in the array, pass it to the grovelling proc passed
----------------------------------------------------------------------------------------*/

void    ZArray::DoForEach(IteratorProcPtr aProc, const long ref)
{
    if (aProc && (numElements > 0))
    {
        long    i = numElements;
        void*    temp = (void*) NewPtr( blkSize );

        FailNIL( temp );

        while ( i )
        {
            GetArrayItem( temp, i);
            (*aProc)(temp, ref);

            // in case the proc changed the item, set it back

            SetArrayItem( temp, i--);
        }

        DisposePtr((Ptr) temp);
    }
}


/*-------------------------------------***  SORT  ***-----------------------------------*/
/*
sort the items in the array into order. The supplied comparison function allows you to
sort anything based on any ordering criteria. Uses a very fast shellsort algorithm. Your
sort function needs to examine the relevant criteria in the items passed, and decide what
order they come in. It should return -1 if a < b, +1 if a > b, and 0 if equal. <ref> can be
anything you want- it is simply passed to the compare function. It might be another object
for example (hint, hint!).

----------------------------------------------------------------------------------------*/

void    ZArray::Sort( register SortCmpProcPtr compareProc, register const long ref )
{
    register long    E,N,M,J,K,R;
    register short    comp;

    register void*    itema;
    register void*    itemb;

    // sanity check- there IS a sort function, right?

    FailOSErr((compareProc == NULL)? paramErr : noErr );

    // allocate some temporary storage

    FailNIL(itema = (void*) NewPtr( blkSize ));
    FailNIL(itemb = (void*) NewPtr( blkSize ));

    // initialise the control variables to the number of elements in the list

    M = E = N = numElements;
    N++;

    // and... sort!

    do
    {
        M /= 2;
        if (M <= 0)
            break;

        K = E - M;
        J = 1;

        do
        {
            N = J;
            do
            {
                R = N + M;
                GetArrayItem( itema, N );                        // get first item
                GetArrayItem( itemb, R );                        // get second item

                comp = (*compareProc)( itema, itemb, ref );        // call the comparison function

                if (comp < 1)                                    // no need to swap (a <= b)
                    break;

                Swap( N, R );                                    // swap items in the array

                N -= M;
            }
            while ( N > 0 );
            J++;
        }
        while (J <= K);
    }
    while( M > 0 );

    // all done, now release the temporary storage

    DisposePtr((Ptr) itema);
    DisposePtr((Ptr) itemb);
}

/*-------------------------------------***  SORT  ***-----------------------------------*/
/*
simpler interface to Sort- indirectly calls the Compare method, which you can override.

----------------------------------------------------------------------------------------*/

void    ZArray::Sort()
{
    Sort( vCompareFunc, (long) this );
}

/*----------------------------------***  COMPARE  ***-----------------------------------*/
/*
compare two items and return their relative ordering: -1 if a < b, +1 if a > b, 0 if a == b.
You need to override this if you wish to use the simple call to Sort() above.
----------------------------------------------------------------------------------------*/

short    ZArray::Compare( void* itema, void* itemb, const long ref )
{
    return 0;
}

/*------------------------------***  INSERTSORTEDITEM  ***------------------------------*/
/*
insert the item into the list at the correct place assuming the list is sorted. This
does a binary search to locate the position, based on the comparison function provided.
Normally the comparison function is the same one you'd use with sort, so everything
agrees. Returns the index poistion it was inserted at.
----------------------------------------------------------------------------------------*/

long    ZArray::InsertSortedItem( void* item, SortCmpProcPtr compareProc, const long ref )
{
    long    pos = BFindIndex( item, compareProc, ref );

    if ( pos > 0 )
        InsertItem( item, pos );

    return pos;
}

/*------------------------------***  INSERTSORTEDITEM  ***------------------------------*/
/*
insert the item into the list at the correct place assuming the list is sorted. This uses
the built in compare function which calls the Compare method.
----------------------------------------------------------------------------------------*/

long    ZArray::InsertSortedItem( void* item, const long ref )
{
    return InsertSortedItem( item, vCompareFunc, ref );
}


/*-----------------------------***  Protected Members  ***------------------------------*/


/*-------------------------------***  INSERTELEMENT  ***--------------------------------*/
/*
make space for one element in the handle
----------------------------------------------------------------------------------------*/

void    ZArray::InsertElement( const long index )
{
    // grow the handle by one element, moving items above <index> up one. This also
    // sets the numElements data member. Index is zero-based.

    long    newSize;

    // check that the index parameter is sensible

    if (index < 0 || index > numElements)
        FailOSErr( kIndexOutOfRangeErr );

    // grow the handle

    newSize = GetHandleSize( a ) + blkSize;
    SetHandleSize(a, newSize);

    FailOSErr(MemError());

    // OK, the handle is now larger by one element- do we need to move any data around?

    if (index < numElements)
    {
        // yes, subsequent entries move up by <blkSize> bytes

        HLock( a );
        BlockMoveData(    *a + (blkSize * index),
                        *a + (blkSize * (index + 1)),
                        blkSize * (numElements - index));
        HUnlock( a );
    }

    // increment the count of elements

    numElements++;
}

/*-------------------------------***  DELETEELEMENT  ***--------------------------------*/
/*
remove space for one element in the handle
----------------------------------------------------------------------------------------*/

void    ZArray::DeleteElement( const long index )
{
    // shrink the handle by one element, after moving entries above <index> down by one.
    // <index> is zero-based.

    // check that the index parameter is sensible

    if (index < 0 || index > numElements)
        FailOSErr( kIndexOutOfRangeErr );

    // one less element

    numElements--;

    // if the index is not the last item, move everything down to fill the space

    if (index < numElements)
    {
        HLock( a );
        BlockMoveData(    *a + (blkSize * (index + 1)),
                        *a + (blkSize * index),
                        blkSize * (numElements - index + 1));
        HUnlock( a );
    }

    // shrink the handle

    SetHandleSize(a, blkSize * numElements);
}


/*--------------------------------***  BINARYSEARCH  ***--------------------------------*/
/*
use the compare function to determine where the item SHOULD be inserted
----------------------------------------------------------------------------------------*/

long    ZArray::BFindIndex( void* item, SortCmpProcPtr compareProc, const long ref )
{
    unsigned long    lowItem, highItem, midItem;
    short            compare;
    void*            itemB;
    long            pos = 1;

    FailNILParam( compareProc );

    lowItem = 0;
    highItem = numElements + 1;

    // if the list is empty, we return item 1, since we can simply append the item.

    if ( numElements < 1 )
        pos = 1;
    else
    {
        // make space for the item we are going to compare

        FailNIL( itemB = (void*) NewPtr( blkSize ));

        while (( highItem - lowItem ) > 1 )
        {
            midItem = ( highItem + lowItem ) >> 1;

            GetArrayItem( itemB, midItem );

            // compare this item to the one we are looking for

            compare = (*compareProc)( item, itemB, ref );

            if ( compare > 0 )
                lowItem = midItem;
            else
                highItem = midItem;
        }

        DisposePtr((Ptr) itemB );
        pos = MAX( midItem, 1 );
    }

    return pos;
}


#pragma mark -
/*--------------------------------***  vCompareFunc  ***--------------------------------*/

static short    vCompareFunc( void* a, void* b, const long ref)
{
    ZArray*        theArray = (ZArray*) ref;

    if ( theArray )
        return theArray->Compare( a, b, ref );
    else
        return 0;
}


/*----------------------------------***  EQUALMEM  ***----------------------------------*/
/*
compare two blocks of memory and return TRUE if they are equal
----------------------------------------------------------------------------------------*/

Boolean        EqualMem( void* a, void* b, const unsigned long length )
{
    Boolean        result = (length > 0);
    Ptr            aa, bb;

    register unsigned long    len = length;

    aa = (Ptr) a;
    bb = (Ptr) b;

    while( len-- )
    {
        if ( *aa++ != *bb++ )
        {
            result = FALSE;
            break;
        }
    }

    return result;
}